{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a6897541-b07c-4609-8ead-71fc1e4179fa",
   "metadata": {},
   "source": [
    "# 斐波那契数列"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9672ab62-76d7-41d7-8b9d-9401a7ee2bf3",
   "metadata": {},
   "source": [
    "## 1、暴⼒递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c288dd67-2cff-496b-ae25-14fc16a8a412",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(N):\n",
    "    if (N == 1 or N == 2):\n",
    "        return 1\n",
    "    return fib(N - 1) + fib(N - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "48781562-48e9-440c-bdd0-aae23684747c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.8 ms ± 17.4 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4288040-0526-4b75-8fe9-a80353b8786b",
   "metadata": {},
   "source": [
    "## 2、带备忘录的递归解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "923fa85e-6cf5-4fc5-8d00-7e0aea911ee6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(N):\n",
    "    if N < 1:\n",
    "        return 0\n",
    "\n",
    "    memo = [0]*(N + 1)\n",
    "    return fib_helper(memo, N)\n",
    "\n",
    "def fib_helper(memo, n):\n",
    "    if (n == 1 or n == 2):\n",
    "        return 1\n",
    "\n",
    "    if memo[n] != 0:\n",
    "        return memo[n]\n",
    "\n",
    "    memo[n] = fib_helper(memo, n - 1) + fib_helper(memo, n - 2)\n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c9fb91cd-fc9e-40e0-8237-601325a22069",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.47 μs ± 45.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cddb854-3c51-463d-b7fe-208e708a5a46",
   "metadata": {},
   "source": [
    "## 3、dp 数组的迭代解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cc1548df-8b54-431f-a72d-2ef859b8b025",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(N):\n",
    "    dp = [0]*(N + 1)\n",
    "    dp[1] = dp[2] = 1\n",
    "    for i in range(3, N+1):\n",
    "        dp[i] = dp[i - 1] + dp[i - 2]\n",
    "        \n",
    "    return dp[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9c617633-2e69-400e-8414-227a83327c82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "931 ns ± 22.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d9a96d84-29f2-4f60-9cec-db25845b2216",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if (n == 2 or n == 1):\n",
    "        return 1\n",
    "\n",
    "    prev = 1\n",
    "    curr = 1\n",
    "    for i in range(n+1):\n",
    "        sum = prev + curr\n",
    "        prev = curr\n",
    "        curr = sum\n",
    "\n",
    "    return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "a724eb3e-d85c-40a9-8ca0-d95cbec281f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "504 ns ± 5.74 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c111f6e2-9592-4820-bddb-7f7331651d17",
   "metadata": {},
   "source": [
    "参考资料：\n",
    "- 《labuladong的算法秘籍》：⼀、斐波那契数列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d2cb525-fe1d-450e-8f48-7d3d3f767df4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
